{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Valid Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效子数组的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组&nbsp;<code>nums</code>&nbsp;，返回满足下面条件的&nbsp;<em>非空、连续</em><strong>&nbsp;子数组</strong>的数目：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>子数组&nbsp;</strong>是数组的 <strong>连续</strong> 部分。</li>\n",
    "\t<li><em>子数组最左边的元素不大于子数组中的其他元素</em>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,4,2,5,3]\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>有 11 个有效子数组，分别是：[1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,1]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>有 3 个有效子数组，分别是：[3],[2],[1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,2]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>有 6 个有效子数组，分别为是：[2],[2],[2],[2,2],[2,2],[2,2,2] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-valid-subarrays](https://leetcode.cn/problems/number-of-valid-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-valid-subarrays](https://leetcode.cn/problems/number-of-valid-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,2,5,3]', '[3,2,1]', '[2,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int], res = 0) -> int:\n",
    "        stack = []\n",
    "        for num in nums:\n",
    "            while stack and num < stack[-1]:\n",
    "                stack.pop()\n",
    "            stack.append(num)\n",
    "            res += len(stack)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "    \n",
    "        # initialize a count array with 0\n",
    "        count = [0] * n\n",
    "        \n",
    "        # iterate through the nums array\n",
    "        for i in range(n):\n",
    "            # start from the current index and move rightward\n",
    "            # until a smaller element is found\n",
    "            j = i\n",
    "            while j < n and nums[j] >= nums[i]:\n",
    "                j += 1\n",
    "            \n",
    "            # number of subarrays with nums[i] as the leftmost smallest element\n",
    "            count[i] = j - i\n",
    "        \n",
    "        # return the sum of counts\n",
    "        return sum(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        nums += [-1]\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] > x:\n",
    "                ans += i - stack.pop()\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        nums.append(-1)\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                res +=  i - stack.pop()\n",
    "            stack.append(i)\n",
    "        \n",
    "        #for i in stack:\n",
    "            #res += len(nums) - i\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        count = len(nums)\n",
    "\n",
    "        for num in nums:\n",
    "            while stack and stack[-1] > num:\n",
    "                stack.pop()\n",
    "            count += len(stack)\n",
    "            stack.append(num)\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "               ans += i - (stack[-1] + 1) + 1\n",
    "               stack.pop()\n",
    "            stack.append(i)\n",
    "        while stack:\n",
    "            ans += n - 1 - (stack[-1]) + 1\n",
    "            stack.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stack = [n]\n",
    "        nums.append(-1)\n",
    "        cnt = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            cnt += stack[-1] - i\n",
    "            stack.append(i)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "               ans += i - (stack[-1] + 1) + 1\n",
    "               stack.pop()\n",
    "            stack.append(i)\n",
    "        while stack:\n",
    "            ans += ( n - 1 - stack[-1] + 1)\n",
    "            stack.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        # dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(0,n):\n",
    "            # dp = [0] * n\n",
    "            for j in range(i,n):\n",
    "                if nums[i] <= nums[j]:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    break           \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        stack = []  # 反向单调递增栈\n",
    "        res = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            while stack and nums[i] <= nums[stack[-1]]:  # 弹掉右边所有比自己大的元素\n",
    "                stack.pop()\n",
    "            r = stack[-1] if stack else len(nums)\n",
    "            res += r - i\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "\n",
    "        for i in range(len(nums) - 1):\n",
    "            right = i + 1\n",
    "            while right < len(nums) and nums[i] <= nums[right]:\n",
    "                count += 1\n",
    "                right += 1\n",
    "        \n",
    "        return len(nums) + count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                ans += (i - stack[-1])\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        # 一个从底到顶单调递增的stack，单调递增栈\n",
    "        # 每个元素作为队列的最后一个元素，都应该计算这些元素作为数组最后一个元素的合法扩展范围\n",
    "        while stack:\n",
    "            # 意思就是stack.pop()可以和左边的任何一个元素组成一个合法数组\n",
    "            ans += n - stack.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stack = [n]\n",
    "        nums.append(-1)\n",
    "        cnt = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            cnt += stack[-1] - i\n",
    "            stack.append(i)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(0,n):\n",
    "            for j in range(i,n):\n",
    "                if nums[i] <= nums[j]:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    break           \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        # 最左边第一个小于这个数字的下标\n",
    "        n = len(nums)\n",
    "        st = [(n, -inf)]\n",
    "        ans = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while nums[i] <= st[-1][1]:\n",
    "                st.pop()\n",
    "            ans += st[-1][0] - i\n",
    "            st.append((i, nums[i]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for l in range(n):\n",
    "            for r in range(l, n):\n",
    "                if nums[r] < nums[l]:\n",
    "                    break\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        stack = []\n",
    "        count = 0\n",
    "\n",
    "        for num in nums:\n",
    "            while stack and stack[-1] > num:\n",
    "                stack.pop()\n",
    "            stack.append(num)\n",
    "            count += len(stack)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        k=0\n",
    "        res=0\n",
    "        while k<=len(nums)-1:\n",
    "            l=1\n",
    "            while k+l<=len(nums)-1 and nums[k]<=nums[k+l]:\n",
    "                l+=1\n",
    "            k+=1\n",
    "            res+=l\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        nums = nums + [-1]      #哨兵。防止12345不计算\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        inc_stk = []  #哨兵\n",
    "        for i in range(n):\n",
    "            while inc_stk and nums[inc_stk[-1]] > nums[i]:    #单调递增栈，右侧第一个小于当前元素的index\n",
    "                res += i - inc_stk.pop(-1)\n",
    "            inc_stk.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        r = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                t = stack[-1]\n",
    "                ans += t - i\n",
    "                r[i] = t\n",
    "            else:\n",
    "                ans += n - i\n",
    "                r[i] = n\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        st = []\n",
    "        ret = []\n",
    "        for i in range(len(nums)):\n",
    "            idx = len(nums) - 1 - i\n",
    "            curval = nums[idx]\n",
    "            if len(st) == 0:\n",
    "                ret.append(1)\n",
    "                st.append((curval, idx))\n",
    "            else:\n",
    "                while len(st) > 0 and st[-1][0] >= curval:\n",
    "                    st.pop()\n",
    "                if len(st) == 0:\n",
    "                    ret.append(len(nums)-idx    )\n",
    "                else:\n",
    "                    ret.append(st[-1][1] - idx)\n",
    "                st.append((curval, idx))\n",
    "        return sum(ret)\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.validSubarrays([1,4,2,5,3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarrays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right = [n] * n\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[stk[-1]] >= nums[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                right[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        return sum(j - i for i, j in enumerate(right))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
